package com.bang.study.day03.test;


import java.util.*;

/**
 * @Auther: Bang
 * @Date: 2019/9/8 22:58
 * @Description: 347. 前 K 个高频元素
 *
 * 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
 *
 * 示例 1:
 *
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 * 示例 2:
 *
 * 输入: nums = [1], k = 1
 * 输出: [1]
 * 说明：
 *
 * 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
 * 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
 */
public class Solution_347_copy {

    /**
     *  前 K 个高频元素
     * @param nums
     * @param k
     * @return
     */
    public List<Integer> topKFrequent(int[] nums, int k) {
        // 定义map存储num的频率 key:num value;freq
        final HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            hashMap.put(nums[i], hashMap.getOrDefault(nums[i],0) + 1);
        }

        // 底层实现是最小堆
        PriorityQueue<Integer> queue = new PriorityQueue<>(
                (a, b) -> hashMap.get(a) - hashMap.get(b)
        );

        for (Integer key : hashMap.keySet()) {
            queue.add(key); //入队
            if (queue.size()>k){
                queue.poll();
            }
        }

        // build output list
        List<Integer> linkedList = new LinkedList();
        while (!queue.isEmpty()) {
            linkedList.add(queue.poll());
        }
        Collections.reverse(linkedList);
        return linkedList;
    }
}
